#include <stdio.h>
#include <malloc.h>
#define INF 32767    
#define Vmax 100    
typedef  char  VType;     
typedef   int  EType;     
 
typedef  struct
{
      VType  vexs[Vmax];         
	  EType  edges[Vmax][Vmax];  
	  int  Vnum, Enum;         
}MGraph;
typedef struct node
{
    EType  adjvex;        
    struct node *next;   
    int weight;     
}EdgeNode;
typedef struct
{
    VType vertex;
    EdgeNode *firstedge;  
}VertexNode;
typedef struct
{
    VertexNode vexlist[Vmax];
    int vexnum,arcnum;
}AdjGraph;
/*创建邻接矩阵*/
void creatGraph(MGraph &G)
{
    int i,j,from,to;
    printf("请输入顶点的个数和边的条数：\n");
    scanf("%d %d",&G.Vnum,&G.Enum);
    getchar();
    printf("请输入顶点：\n");
    for(i=0;i<G.Vnum;i++)
    {
        scanf("%c",&G.vexs[i]);
    }
    getchar();
 
    for (i=0;i<G.Vnum;i++)       
    {
        for(j=0;j<G.Vnum;j++)
        {
            G.edges[i][j]=INF;
        }
    }
    printf("请输入之间存在边的顶点（两两输入）：\n");
    for(i=0;i<G.Enum;i++)
    {
    	int weight; 
        char F,T;
        printf("第%d对：",i+1);
        scanf("%c %c %d",&F,&T,&weight);  
        getchar();
        for (from=0;from<G.Vnum;from++)
        {
            if(G.vexs[from]==F)
                for(to=0;to<G.Vnum;to++)
                {
                  if(G.vexs[to]==T)
                      G.edges[from][to] = weight;
                }
        }
        printf("\n");
    } 
     printf("图G的邻接矩阵：\n");
     for (i=0;i<G.Vnum;i++)
    {
        for(j=0;j<G.Vnum;j++)
        {
 
            printf("%d\t",G.edges[i][j]);
 
        }
        printf("\n");
    }
}
/*将邻接矩阵转化为邻接表*/
void MatToList(MGraph G,AdjGraph *& g)
{
    int i,j;
    EdgeNode * p;
    g =(AdjGraph *)malloc(sizeof(AdjGraph));
    for(i=0;i<G.Vnum;i++)
        g->vexlist[i].firstedge=NULL;  
    for(i=0;i<G.Vnum;i++)
        for(j=G.Vnum-1;j>=0;j--)       
            if(G.edges[i][j]!=INF)
            {
                p=(EdgeNode *)malloc(sizeof(EdgeNode));
                p->adjvex=j;
                p->next=g->vexlist[i].firstedge;  
                g->vexlist[i].firstedge=p;
            }
     g->vexnum=G.Vnum; G.Enum=g->arcnum;
     printf("图G的邻接表：\n");
     for(i=0;i<g->vexnum;i++)
     {
         p=g->vexlist[i].firstedge;
         printf("%c->",G.vexs[i]);
         while(p!=NULL)
         {
             printf("%d->",p->adjvex);
             p=p->next;
         }
         printf("NULL\n");
     }
}
 
void DestroyAdj(AdjGraph *&G)  
{ int i;
 EdgeNode *pre,*p;
 for (i=0;i<G->vexnum;i++)   
 { pre=G->vexlist[i].firstedge; 
  if (pre!=NULL)
  { p=pre->next;
   while (p!=NULL)   
   { free(pre);
    pre=p; p=p->next;
   }
   free(pre);
  }
 }
 free(G);     
}
 
int main()
{
 MGraph G;
 AdjGraph *g;
 creatGraph(G);   
 
 printf("将g转换为邻接表G\n");
 MatToList(G,g);    
 DestroyAdj(g);    
return 1;
}
 
 
 
 